Solving job scheduling problems is a difficult task for humans because of the number of alternatives that must be considered in the search for a solution. Various programming techniques have been devised to use computers to solve scheduling problems. Most of these techniques work well when the problem is relatively simple (e.g., when the jobs can be processed by any of the devices available). However, when the problem becomes more complex, traditional programming techniques lose their effectiveness. In particular, generating job schedules for printing workflows is complex because such workflows include a number of constraints, such that certain jobs can be processed only by particular devices at particular times, some jobs must be processed before others, and users may prefer solutions of a certain kind over others. Conventional techniques, such as C, C++, or Java programming, require complex programs, which are difficult and time-consuming to write, debug, and maintain, due to their relatively low level of abstraction.
In recent years, powerful declarative languages have been designed that allow solving industrial-size problems by programming at a higher level of abstraction. Programmers using such declarative languages essentially describe the problems and the properties of the desired solutions, and let general-purpose programs, called solvers, find the solutions satisfying the given constraints. It is important to stress that the programmer no longer specifies how to compute the solution. Rather, the solver, when executed by a data processing system, takes care of that.
Most declarative languages have thus far been focused on either quantitative problems (e.g. finding solutions to sets of sophisticated equations) or qualitative problems (e.g. determining how to perform discrete actions on a physical system, such as an electrical circuit, to obtain a certain macroscopic effect, such as lighting certain bulbs), but not both. Among the most promising programming methodologies are the constraint satisfaction paradigm, which allows describing equations and inequalities among variables of interest, and the Answer Set Programming (ASP) paradigm, which describes properties of objects and the relations among them using a simple logical language.
The basic definition of the syntax and semantics of the language of ASP states that an ASP program or answer set program is a set of rules, a rule being a statement of the form:H←L1, . . . ,Lm,not Lm+1, . . . ,not Ln  (1)where H and Li are first order literals, and “not” is the so-called default negation operator, which is well-known known in the art. For more details, see the definitions provided by Michael Gelfond and Vladimir Lifschitz in the article “Classical negation in logic programs and disjunctive databases” (New Generation Computing, Vol. 9, pp. 365-385, 1991). Most solvers for ASP are based on the Davis-Putnam-Logemann-Loveland (DPLL) algorithm described by M. Davis and H. Putnam in the article “A computing procedure for quantification theory” (Communications of the ACM, Vol. 7, pp. 201-215, 1960); and by M. Davis, G. Logemann, and D. Loveland in the article “A machine program for theorem proving” (Communications of the ACM, Vol. 5, pp., 394-397, 1962). For simplicity, we refer to these solvers by the term “DPLL-type solvers”. Among the DPLL-type solvers for ASP, one of the most powerful is the SMODELS solver described by P. Simons, I. Niemela and T. Soininen in the article “Extending and implementing the stable model semantics” (Artificial Intelligence, Vol. 138, pp. 181-234, 2002).
Of the programming methodologies mentioned above, constraint satisfaction has been shown to provide elegant solutions to industrial-size problems whose nature is mostly quantitative, whereas ASP has been used to solve industrial-size problems whose nature is mostly qualitative. However, certain complex scheduling problems, such as those for the printing workflow, involve both quantitative aspects (e.g. the start times of execution of the jobs) and qualitative aspects (e.g. required order of execution among jobs, preferences for solutions having certain properties). For this reason, scheduling problems of this kind can be tackled by combining answer set programming and constraint satisfaction.
Notice that, in this case, the performance of the overall system depends on the performance of both the constraint solver and of the ASP solver used. Unfortunately, although ASP solvers have improved significantly over the last two decades, their performance is still rather unstable. ASP solvers can often solve a problem in a matter of seconds, but may take hours or days to solve a slightly different problem of similar difficulty. This instability is problematic for industrial applications, where users typically expect consistent performance.
Consequently, a need exists for a method of solving scheduling problems in general, and those related to the printing workflow, using ASP solvers that ensures a consistent, reliable performance.